RP (복잡도)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
RP(Randomized Polynomial time)는 확률적 튜링 기계 또는 결정적 튜링 기계를 사용하여 정의되는 계산 복잡도 클래스이다. RP에 속하는 언어는 다항 시간 내에 실행되며, 입력이 언어에 속할 경우 1/2 이상의 확률로 1을 출력하고, 그렇지 않은 경우 0을 출력하는 확률적 튜링 기계가 존재한다. 결정적 튜링 기계 정의에서는, 입력이 언어에 속할 경우 특정 길이의 문자열에 대해 1을 출력하는 비율이 1/2 이상이어야 한다. RP는 co-RP, BPP, ZPP 등과 관련되며, P, NP, co-NP와의 관계는 아직 밝혀지지 않았다. 다항식 항등식 검사가 RP에 속하는 문제의 예시로 제시된다.
더 읽어볼만한 페이지
| RP (복잡도) | |
|---|---|
| 개요 | |
| 범주 | BPP |
| 완전 문제 | 알려지지 않음 |
| 정의 | 문제에 대한 확률적 알고리즘이 존재한다. 알고리즘은 다항 시간 안에 실행된다. 입력이 "예"인 경우, 알고리즘은 적어도 1/2의 확률로 "예"를 반환한다. 입력이 "아니오"인 경우, 알고리즘은 항상 "아니오"를 반환한다. |
| 보완 | co-RP |
| 관계 | P ⊆ RP ⊆ NP RP ⊆ BPP RP ⊆ ZPP |
| 설명 | |
| 의미 | RP는 "Randomized Polynomial time"의 약자이다. RP에 속하는 문제는 "예"인 경우, 알고리즘이 무작위 선택을 통해 다항 시간 안에 "예"를 반환할 확률이 적어도 1/2이다. "아니오"인 경우에는 항상 "아니오"를 반환한다. |
| 오류 | RP 알고리즘은 "예"인 경우 오류를 낼 수 있지만, "아니오"인 경우에는 오류를 내지 않는다. 즉, RP는 단측 오류(one-sided error)를 허용하는 확률적 다항 시간 복잡도 부류이다. |
| co-RP | co-RP는 RP의 여집합(complement)에 해당하는 복잡도 부류이다. co-RP에 속하는 문제는 "아니오"인 경우, 알고리즘이 무작위 선택을 통해 다항 시간 안에 "아니오"를 반환할 확률이 적어도 1/2이다. "예"인 경우에는 항상 "예"를 반환한다. |
| 중요성 | RP는 확률적 알고리즘의 효율성을 분석하는 데 중요한 역할을 한다. RP에 속하는 문제는 확률적 알고리즘을 통해 효율적으로 해결할 수 있음을 의미한다. |
| 다른 복잡도 부류와의 관계 | RP는 P, NP, BPP, ZPP 등 다른 복잡도 부류와 관련이 있다. P는 RP의 부분집합이며, RP는 NP의 부분집합이다. RP는 BPP의 부분집합이며, RP는 ZPP의 부분집합이다. |
| 수학적 정의 | |
| 정의 | 언어 L이 다음 조건을 만족하는 확률적 다항 시간 알고리즘 A가 존재하면, L은 RP에 속한다. |
| 조건 1 | 입력 문자열 x가 L에 속하지 않으면, A(x)는 항상 "아니오"를 반환한다. |
| 조건 2 | 입력 문자열 x가 L에 속하면, A(x)는 적어도 1/2의 확률로 "예"를 반환한다. |
| 오류 감소 | |
| 오류 감소 | RP 알고리즘의 오류 확률은 반복 실행을 통해 줄일 수 있다. 알고리즘을 n번 반복 실행하고, 그 중 하나라도 "예"를 반환하면 "예"를 반환하고, 그렇지 않으면 "아니오"를 반환한다. 이 경우 오류 확률은 2-n으로 줄어든다. |
2. 정의
RP는 확률적 튜링 기계 또는 결정적 튜링 기계를 사용하여 정의할 수 있다.[1]
확률적 튜링 기계를 사용한 정의는 다음과 같다. 언어 ''L''이 RP에 속한다는 것은 다음 조건을 만족하는 확률적 튜링 기계 ''M''이 존재한다는 것을 의미한다.
- ''M''은 모든 입력에 대해 다항 시간 내에 실행된다.
- ''L''에 속하는 모든 ''x''에 대해, ''M''은 1을 출력할 확률이 1/2 이상이다.
- ''L''에 속하지 않는 모든 ''x''에 대해, ''M''은 0을 출력한다.
결정적 튜링 기계를 사용한 정의는 다음과 같다. 언어 ''L''이 RP에 속한다는 것은 다음 조건을 만족하는 다항식 ''p''와 결정적 튜링 기계 ''M''이 존재한다는 것을 의미한다.
- ''M''은 모든 입력에 대해 다항 시간 p 내에 실행된다.
- ''L''에 속하는 모든 ''x''에 대해, M(''x'',''y'') = 1을 만족하는 길이 ''p''(|''x''|)의 문자열 ''y''의 비율이 1/2 이상이다.
- ''L''에 속하지 않는 모든 ''x''에 대해, 그리고 길이 ''p''(|''x''|)의 모든 문자열 ''y''에 대해, M(''x'',''y'') = 0이다.
이 정의에서 문자열 ''y''는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 출력을 나타낸다. 일부 응용 분야에서는 이 정의가 확률적 튜링 기계를 언급하지 않으므로 더 선호된다.[1]
2. 1. 확률적 튜링 기계 정의
언어 ''L''이 '''RP'''에 속한다는 것은 다음과 같은 조건을 만족하는 확률적 튜링 기계 ''M''이 존재한다는 것을 의미한다.[1]- ''M''은 모든 입력에 대해 다항 시간 내에 실행된다.
- ''L''에 속하는 모든 ''x''에 대해, ''M''은 1을 출력할 확률이 1/2 이상이다.
- ''L''에 속하지 않는 모든 ''x''에 대해, ''M''은 0을 출력한다.
또는, '''RP'''는 결정적 튜링 기계를 사용하여 정의할 수 있다. 언어 ''L''이 '''RP'''에 속한다는 것은 다음과 같은 조건을 만족하는 다항식 ''p''와 결정적 튜링 기계 ''M''이 존재한다는 것을 의미한다.[1]
- ''M''은 모든 입력에 대해 다항 시간 p 내에 실행된다.
- ''L''에 속하는 모든 ''x''에 대해, M(''x'',''y'') = 1을 만족하는 길이 ''p''(|''x''|)의 문자열 ''y''의 비율이 1/2 이상이다.
- ''L''에 속하지 않는 모든 ''x''에 대해, 그리고 길이 ''p''(|''x''|)의 모든 문자열 ''y''에 대해, M(''x'',''y'') = 0이다.
이 정의에서 문자열 ''y''는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 출력을 나타낸다. 일부 응용 분야에서는 이 정의가 확률적 튜링 기계를 언급하지 않으므로 더 선호된다.[1]
2. 2. 결정적 튜링 기계 정의
언어 ''L''이 '''RP'''에 속한다는 것은 다음 조건을 만족하는 다항식 ''p''와 결정적 튜링 기계 ''M''이 존재한다는 것을 의미한다.- ''M''은 모든 입력에 대해 다항 시간 p 내에 실행된다.
- ''L''에 속하는 모든 ''x''에 대해, M(''x'',''y'') = 1을 만족하는 길이 ''p''(|''x''|)의 문자열 ''y''의 비율이 1/2 이상이다.
- ''L''에 속하지 않는 모든 ''x''에 대해, 그리고 길이 ''p''(|''x''|)의 모든 문자열 ''y''에 대해, M(''x'',''y'') = 0이다.
이 정의에서 문자열 ''y''는 확률적 튜링 기계가 수행했을 무작위 동전 던지기의 출력을 나타낸다. 일부 응용 분야에서는 이 정의가 확률적 튜링 기계를 언급하지 않으므로 더 선호된다.
3. 관련 복잡도 종류
RP에 속하는 문제는 '예'라는 답이 나오면 언제나 옳지만, '아니오'라는 답이 나오면 대체로 옳다. co-RP는 이와 반대로 '아니오'라는 답이 나올 때는 항상 옳지만, '예'라는 답이 나올 때는 대체로 옳다. BPP는 '예', '아니오' 모두 잘못된 답이 나올 수 있는 알고리즘의 집합이다. RP와 co-RP의 교집합은 ZPP이다.
일부에서는 RP를 R, co-RP를 co-R이라고 부르기도 한다.
3. 1. co-RP
co-RP는 '아니오'라는 답이 나오는 경우는 항상 옳지만, '예'라는 답이 나오는 경우는 일정 확률로 틀릴 수 있는 문제의 집합이다. RP와는 반대되는 개념이다.[1] 일부에서는 RP를 R이라고 하는 경우가 있는데, 이때 마찬가지로 co-RP를 co-R이라고 부른다.[1]3. 2. BPP
BPP는 '예'와 '아니오' 답 모두 일정 확률로 틀릴 수 있는 알고리즘의 집합이다. RP와 co-RP를 모두 포함한다.3. 3. ZPP
RP와 co-RP의 교집합은 ZPP이다.[1] ZPP는 항상 옳은 답을 출력하지만, 평균 실행 시간이 다항 시간인 알고리즘의 집합이다.[1]4. P-NP 문제와 연관성
P는 RP의 부분집합이며, RP는 NP의 부분집합이다. 마찬가지로 P는 co-RP의 부분집합이고, co-RP는 co-NP의 부분집합이다. 이러한 부분집합 관계가 진부분집합인지는 아직 밝혀지지 않았다. 즉, P=RP, RP=NP, RP=co-RP인지, RP가 NP와 co-NP의 교집합에 포함되는지 등은 미해결 문제이다. 하지만, P≠RP이거나 RP≠NP일 것으로 추측되며, P=NP가 성립하지 않을 것으로 예상된다.
RP는 입력 크기에 의존하지 않는 일정한 비율의 계산 경로가 수락될 경우, 그 입력을 수락하는 비결정적 튜링 기계로 인식 가능한 문제의 집합으로 정의할 수 있다. 반면 NP는 하나의 계산 경로만 수락되면 되므로, RP가 NP의 부분집합임이 명확하다.
4. 1. 다항식 항등식 검사
co-RP에 속하지만 현재 P에 속하는 것으로 알려지지 않은 문제의 예시로는 다항식 항등식 검사가 있는데, 이는 정수 위에서 주어진 다변수 산술 표현식이 영-다항식인지 여부를 결정하는 문제이다. 예를 들어, ''x''·''x'' − ''y''·''y'' − (''x'' + ''y'')·(''x'' − ''y'')는 영-다항식이지만, ''x''·''x'' + ''y''·''y''는 그렇지 않다.5. 비결정적 튜링 기계
RP는 입력 크기와 상관없이 적어도 일정 비율의 계산 경로가 허용될 경우 기계가 허용하는 비결정적 튜링 기계로 인식할 수 있는 문제들의 집합이다. 이는 NP가 단 하나의 허용 경로만 필요하며, 이는 경로의 지수적으로 작은 비율을 구성할 수 있다는 점과 대조된다. 이러한 특징 때문에 RP가 NP의 부분 집합이라는 사실이 명백해진다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com